package main.leetcode.clockin.May;

import java.util.Stack;

/**
 * 394.字符串解码
 *
 * <p>给定一个经过编码的字符串，返回它解码后的字符串。
 *
 * <p>编码规则为: k[encoded_string]，表示其中方括号内部的 encoded_string 正好重复 k 次。注意 k 保证为正整数。
 *
 * <p>你可以认为输入字符串总是有效的；输入字符串中没有额外的空格，且输入的方括号总是符合格式要求的。
 *
 * <p>此外，你可以认为原始数据不包含数字，所有的数字只表示重复的次数 k ，例如不会出现像 3a 或 2[4] 的输入。
 *
 * <p>示例: s = "3[a]2[bc]", 返回 "aaabcbc". s = "3[a2[c]]", 返回 "accaccacc". s = "2[abc]3[cd]ef", 返回
 * "abcabccdcdcdef".
 *
 * <p>来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/decode-string
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class day28 {
    public static void main(String[] args) {
        System.out.println(new day28().decodeString("3[a]2[bc]"));
        System.out.println(new day28().decodeString("3[a2[c]]"));
        System.out.println(new day28().decodeString("2[abc]3[cd]ef"));
    }

    public String decodeString(String s) {
        return decodeString(s, 1, 0, s.length() - 1);
    }

    private String decodeString(String s, int time, int i, int j) {
        StringBuilder res = new StringBuilder();
        Stack<Integer> bracket = new Stack<>();
        StringBuilder num = new StringBuilder();
        char c;
        int start, end;
        for (int k = i; k <= j; ++k) {
            c = s.charAt(k);
            // 左括号，入栈
            if (c == '[') {
                bracket.push(k);
            }
            // 右括号，出栈，同时记录左括号的位置和右括号的位置
            else if (c == ']') {
                start = bracket.pop();
                end = k;
                // 弹出后栈空说明这是一个有效括号串，对其中的字符串进行递归解码
                if (bracket.isEmpty()) {
                    res.append(
                            decodeString(s, Integer.parseInt(num.toString()), start + 1, end - 1));
                    num.delete(0, num.length());
                }
            }
            // 拼接数字
            else if (bracket.isEmpty() && c >= '0' && c <= '9') {
                num.append(c);
            }
            // 拼接无需解码的字符
            else if (bracket.isEmpty()) {
                res.append(c);
            }
        }
        String tmp = res.toString();
        for (int k = 0; k < time - 1; ++k) {
            res.append(tmp);
        }
        return res.toString();
    }
}
